﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.DoubleEndedPriorityMaps;
using Algoritmia.Problems.Sorting;
using Algoritmia.Utils;


namespace Algoritmia.Problems.Knapsack.BranchAndBound
{
    public class KnapsackSolver3 : IKnapsackSolver
    {
        private readonly DataStructures.Lists.IList<int> _weights;
        private readonly DataStructures.Lists.IList<double> _values;
        private readonly int _n;
        private readonly IInPlaceSorter<Tuple<int, double>> _sorter;

        #region Inner class
        public class State : IComparable<State>
        {
            public double Score { get; private set; }
            public double KnownValue { get; private set; }
            public DataStructures.Lists.IList<int> Decisions { get; private set; }

            public State(double score, double knownValue, DataStructures.Lists.IList<int> decisions)
            {
                Score = score;
                KnownValue = knownValue;
                Decisions = decisions;
            }

            #region Implementation of IComparable<in State>

            public int CompareTo(State other)
            {
                return Score.CompareTo(other.Score);
            }

            #endregion
        }
        #endregion

        public KnapsackSolver3(DataStructures.Lists.IList<int> weights, DataStructures.Lists.IList<double> values, Func<IInPlaceSorter<Tuple<int,double>>> createSorter = null)
        {
            _weights = weights;
            _values = values;
            _n = _values.Count;
            createSorter = createSorter ?? (() => new BasicInPlaceQuickSorter<Tuple<int, double>>());
            _sorter = createSorter();
        }

        public static double FractionalKnapsackProfit(DataStructures.Lists.IList<int> weights, 
                                                      DataStructures.Lists.IList<double> values, 
                                                      double W, IInPlaceSorter<Tuple<int,double>> sorter)
        {
            var weightsList = weights.Select((e, i) => new Tuple<int, double>(i, values[i] / e)).ToAlgoritmiaList();
            sorter.Sort(weightsList, (tp1, tp2) => tp1.Item2.CompareTo(tp2.Item2));
            double score = 0.0;
            foreach (var tple in weightsList.Reverse())
            {
                var i = tple.Item1;
                var ratio = Math.Min(1.0, W / weights[i]);
                score += ratio*values[i];
                W -= ratio*weights[i];
            }
            return score;
        }

        public DataStructures.Lists.IList<int> Solve(int W)
        {
            var open = new MaxMinIntervalHeapMap<Tuple<int, int>, State>(from c in Enumerable.Range(0, W + 1)
                                                                   select new KeyValuePair<Tuple<int, int>, State>(
                                                                            new Tuple<int, int>(0, c),
                                                                            new State(FractionalKnapsackProfit(_weights, _values, W - c, _sorter),
                                                                                0.0, new int[] {}.ToAlgoritmiaList())));
            var ramifications = new[] { 0, 1 };
            DataStructures.Lists.IList<int> solution = null;
            double optimalValue = double.NegativeInfinity;
            while (open.Count > 0)
            {
                var kv = open.ExtractOptimal();
                var n = kv.Key.Item1;
                var c = kv.Key.Item2;
                var s = kv.Value;
                foreach (var decision in ramifications)
                {
                    var x = s.Decisions.Concat(new[] { decision }).ToAlgoritmiaList();
                    var knownValue = s.KnownValue + decision*_values[n];
                    if (n+1 == _n)
                    {
                        if (c + decision*_weights[n] <= W && knownValue > optimalValue)
                        {
                            solution = x;
                            optimalValue = knownValue;
                            while ( open.Count > 0 && open.GetWorstValue().Score <= optimalValue)
                            {
                                open.ExtractWorst();
                            }
                        }
                    }
                    else if ( c + decision * _weights[n] <= W)
                    {
                        var n1 = n + 1;
                        var c1 = c + decision*_weights[n];
                        var score = knownValue +
                                    FractionalKnapsackProfit(_weights.Where((e, i) => i >= n1).ToAlgoritmiaList(),
                                                             _values.Where((e, i) => i >= n1).ToAlgoritmiaList(),
                                                             W - c1, _sorter);
                        if ( open.Contains(new Tuple<int, int>(n1,c1)))
                        {
                            if (open[new Tuple<int, int>(n1, c1)].Score < score)
                            {
                                open.Add(new Tuple<int, int>(n1, c1), new State(score, knownValue, x));
                            }
                        }
                        else
                        {
                            open.Add(new Tuple<int, int>(n1, c1), new State(score, knownValue, x));
                        }
                    }
                }
            }
            return solution;
        }

    }
}
